#include "../include/SeqStack.h"

long fabByRecurison(long n){
	if(n <=1)
		return n;
	else 
		return fabByRecurison(n-1) + fabByRecurison(n-2);
}

long fabByStack(long n){
	SeqStack<long int > s;
	long result =0;
	while(n>=0){
		if(n <=1)
			result +=n;
		else{
			s.Push(n-1);
			s.Push(n-2);
		}
		if(s.Pop(n)==false)
			break;
	}
	return result;
}

long fabByIterator(long n){
	long first,second,current;
	first =0;
	second = 1;
	if(n<=1)
		return n;
	for(int i=2;i<=n;i++){
		current = first + second;
		first = second;
		second = current;
	}
	return current;
}



int main(){
	long n;
	while(cin >>n){
		cout<<"By recurision:"<<fabByRecurison(n)<<endl;	
		cout<<"By stack:"<<fabByStack(n)<<endl;
		cout<<"By Iterator:"<<fabByIterator(n)<<endl;
	}
	return 0;
}
